/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* next;
    Node* random;
    
    Node(int _val) {
        val = _val;
        next = NULL;
        random = NULL;
    }
};
*/

class Solution {
public:
    Node* copyRandomList(Node* head) {
        if(head==nullptr){
            return nullptr;
        }

        //将复制节点插入到原节点之后
        for(Node* cur=head;cur;cur=cur->next->next)
        {
            cur->next=new Node(cur->val,cur->next,nullptr);
        }

        for(Node* cur=head;cur;cur=cur->next->next)
        {
            if(cur->random)
            cur->next->random=cur->random->next;
        }

        //分离
        Node* new_head=head->next;
        Node* cur=head;
        for(;cur->next->next!=nullptr;cur=cur->next){
            Node* ptr=cur->next;
            cur->next=ptr->next;
            ptr->next=ptr->next->next;
        }
        cur->next=nullptr;
        return new_head;

    }
};